import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np
import matplotlib.animation as animation

def init_board(size):
    """
    初始化棋盘
    :param size: 棋盘的边长（2的k次方）
    :return: 初始化后的棋盘
    """
    board = np.zeros((size, size), dtype=int)
    return board

def place_L(board, x, y, L_type, mark):
    """
    在棋盘上放置一个L型骨牌
    :param board: 当前棋盘
    :param x: L型骨牌左上角的x坐标
    :param y: L型骨牌左上角的y坐标
    :param L_type: L型骨牌的类型（0, 1, 2, 3表示四种不同的旋转状态）
    :param mark: 标记L型骨牌的编号
    """
    if L_type == 0:  # ┌
        positions = [(x, y), (x, y+1), (x+1, y)]
    elif L_type == 1:  # ┐
        positions = [(x, y), (x, y+1), (x+1, y+1)]
    elif L_type == 2:  # └
        positions = [(x, y), (x+1, y), (x+1, y+1)]
    elif L_type == 3:  # ┘
        positions = [(x, y+1), (x+1, y), (x+1, y+1)]

    for pos in positions:
        board[pos] = mark

def cover(board, special_x, special_y, top_left_x, top_left_y, size, mark, frames):
    """
    递归覆盖棋盘
    :param board: 当前棋盘
    :param special_x: 特殊方格的x坐标
    :param special_y: 特殊方格的y坐标
    :param top_left_x: 当前子棋盘左上角的x坐标
    :param top_left_y: 当前子棋盘左上角的y坐标
    :param size: 当前子棋盘的边长
    :param mark: 当前使用的标记编号
    :param frames: 用于记录每一步的棋盘状态
    :return: 更新后的标记编号
    """
    if size == 2:
        # 基本情况：2x2棋盘
        mark += 1
        for i in range(2):
            for j in range(2):
                if not (top_left_x + i == special_x and top_left_y + j == special_y):
                    board[top_left_x + i, top_left_y + j] = mark
        frames.append(board.copy())
        return mark

    half_size = size // 2
    mark += 1

    # 确定特殊方格所在的象限，并在中心放置一个L型骨牌
    if special_x < top_left_x + half_size and special_y < top_left_y + half_size:
        place_L(board, top_left_x + half_size - 1, top_left_y + half_size - 1, 0, mark)
        quadrant = 0
    elif special_x < top_left_x + half_size and special_y >= top_left_y + half_size:
        place_L(board, top_left_x + half_size - 1, top_left_y + half_size, 1, mark)
        quadrant = 1
    elif special_x >= top_left_x + half_size and special_y < top_left_y + half_size:
        place_L(board, top_left_x + half_size, top_left_y + half_size - 1, 2, mark)
        quadrant = 2
    else:
        place_L(board, top_left_x + half_size, top_left_y + half_size, 3, mark)
        quadrant = 3

    frames.append(board.copy())

    # 递归覆盖四个象限
    if quadrant == 0:
        mark = cover(board, special_x, special_y, top_left_x, top_left_y, half_size, mark, frames)
        mark = cover(board, top_left_x + half_size - 1, top_left_y + half_size, top_left_x, top_left_y + half_size, half_size, mark, frames)
        mark = cover(board, top_left_x + half_size, top_left_y + half_size - 1, top_left_x + half_size, top_left_y, half_size, mark, frames)
        mark = cover(board, top_left_x + half_size, top_left_y + half_size, top_left_x + half_size, top_left_y + half_size, half_size, mark, frames)
    elif quadrant == 1:
        mark = cover(board, top_left_x + half_size - 1, top_left_y + half_size - 1, top_left_x, top_left_y, half_size, mark, frames)
        mark = cover(board, special_x, special_y, top_left_x, top_left_y + half_size, half_size, mark, frames)
        mark = cover(board, top_left_x + half_size, top_left_y + half_size - 1, top_left_x + half_size, top_left_y, half_size, mark, frames)
        mark = cover(board, top_left_x + half_size, top_left_y + half_size, top_left_x + half_size, top_left_y + half_size, half_size, mark, frames)
    elif quadrant == 2:
        mark = cover(board, top_left_x + half_size - 1, top_left_y + half_size - 1, top_left_x, top_left_y, half_size, mark, frames)
        mark = cover(board, top_left_x + half_size - 1, top_left_y + half_size, top_left_x, top_left_y + half_size, half_size, mark, frames)
        mark = cover(board, special_x, special_y, top_left_x + half_size, top_left_y, half_size, mark, frames)
        mark = cover(board, top_left_x + half_size, top_left_y + half_size, top_left_x + half_size, top_left_y + half_size, half_size, mark, frames)
    else:
        mark = cover(board, top_left_x + half_size - 1, top_left_y + half_size - 1, top_left_x, top_left_y, half_size, mark, frames)
        mark = cover(board, top_left_x + half_size - 1, top_left_y + half_size, top_left_x, top_left_y + half_size, half_size, mark, frames)
        mark = cover(board, top_left_x + half_size, top_left_y + half_size - 1, top_left_x + half_size, top_left_y, half_size, mark, frames)
        mark = cover(board, special_x, special_y, top_left_x + half_size, top_left_y + half_size, half_size, mark, frames)

    return mark

def visualize_board(frames, size):
    """
    可视化棋盘覆盖过程
    :param frames: 记录每一步棋盘状态的列表
    :param size: 棋盘的边长
    """
    fig, ax = plt.subplots()

    def update(frame):
        ax.clear()
        ax.set_xticks(np.arange(-.5, size, 1), minor=True)
        ax.set_yticks(np.arange(-.5, size, 1), minor=True)
        ax.grid(which='minor', color='black', linestyle='-', linewidth=2)
        ax.imshow(frame, cmap='tab20c', vmin=0, vmax=np.max(frame))

    ani = animation.FuncAnimation(fig, update, frames=frames, repeat=False)
    plt.show()

def main(size, special_x, special_y):
    """
    主函数，初始化棋盘并调用覆盖和可视化函数
    :param size: 棋盘的边长
    :param special_x: 特殊方格的x坐标
    :param special_y: 特殊方格的y坐标
    """
    board = init_board(size)
    board[special_x, special_y] = -1  # 标记特殊方格
    frames = [board.copy()]
    mark = 0
    cover(board, special_x, special_y, 0, 0, size, mark, frames)
    visualize_board(frames, size)

# 设置棋盘大小和特殊方格位置，并运行主函数
main(8, 3, 3)
